package br.ufrj.dcc.org2.lisch;

public class HashTable {
	private DataItem[] hashArray; // array de data items
	private int arraySize;
	private DataItem nonItem; // para itens apagados
	// teste

	public HashTable(int size) // construtor
	{
		arraySize = size;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1); // chave do item deletado eh -1
	}

	public void displayTable() {
		System.out.print("Tabela: ");
		for (int j = 0; j < arraySize; j++) {
			if (hashArray[j] != null)
				System.out.print(hashArray[j].getKey() + " ");
			else
				System.out.print("** ");
		}
		System.out.println("");
	}

	public int hashFunc(int key) {
		return key % arraySize; // funcao de hash 
	}

	// TODO: Quando a tabela esta cheia, o loop do while se torna infinito! Arrumar isso... 
	public void insert(DataItem item) // insere um item
	// (assume q a tabela nao esta lotada)
	{
		int key = item.getKey(); // extrai chave
		int hashVal = hashFunc(key); // hasheia a chave
		// ate achar espaco vazio ou item coalescido (marcado com -1),
		if (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
			hashVal = arraySize - 1;
			while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
				--hashVal; // vai para a proxima celula
				if (hashVal == -1) {
					System.out.println("Tabela Cheia...");
					return;
				}
			}
		}
		hashArray[hashVal] = item; // insere item
	}
	
	public DataItem delete(int key) // deleta um DataItem
	{
		int hashVal = hashFunc(key); // hasheia a chave
		int hashSize = arraySize;

		while (hashArray[hashVal] != null) // ate achar uma celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal]; // salva item
				hashArray[hashVal] = nonItem; // deleta item
				return temp; // retorna o item
			}
			--hashSize; // vai pra celula anterior
			hashVal = hashSize; // seta o valor do ultimo elemento
			if (hashSize == -1) break; // Nao achou, sai do loop
		}
		return null; // nao achou o item :(
	} 

	public DataItem find(int key) // acha o item dando uma key
	{
		int hashVal = hashFunc(key); // hasheia a chave
		
		int hashSize = arraySize;
		
		while (hashArray[hashVal] != null) // ata achar celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal]; // Sim! retorna o cara
			--hashSize; // vai pra celula anterior
			hashVal = hashSize; // seta o valor do ultimo elemento
			if (hashSize == -1) break; // Nao achou, sai do loop
		}
		return null; // nao achou o cara :(
	}
}